{
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "## 2.19 \u5b9e\u73b0\u4e00\u4e2a\u7b80\u5355\u7684\u9012\u5f52\u4e0b\u964d\u5206\u6790\u5668\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "### \u95ee\u9898\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "\u4f60\u60f3\u6839\u636e\u4e00\u7ec4\u8bed\u6cd5\u89c4\u5219\u89e3\u6790\u6587\u672c\u5e76\u6267\u884c\u547d\u4ee4\uff0c\u6216\u8005\u6784\u9020\u4e00\u4e2a\u4ee3\u8868\u8f93\u5165\u7684\u62bd\u8c61\u8bed\u6cd5\u6811\u3002\n\u5982\u679c\u8bed\u6cd5\u975e\u5e38\u7b80\u5355\uff0c\u4f60\u53ef\u4ee5\u4e0d\u53bb\u4f7f\u7528\u4e00\u4e9b\u6846\u67b6\uff0c\u800c\u662f\u81ea\u5df1\u5199\u8fd9\u4e2a\u89e3\u6790\u5668\u3002"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "### \u89e3\u51b3\u65b9\u6848\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "\u5728\u8fd9\u4e2a\u95ee\u9898\u4e2d\uff0c\u6211\u4eec\u96c6\u4e2d\u8ba8\u8bba\u6839\u636e\u7279\u6b8a\u8bed\u6cd5\u53bb\u89e3\u6790\u6587\u672c\u7684\u95ee\u9898\u3002\n\u4e3a\u4e86\u8fd9\u6837\u505a\uff0c\u4f60\u9996\u5148\u8981\u4ee5BNF\u6216\u8005EBNF\u5f62\u5f0f\u6307\u5b9a\u4e00\u4e2a\u6807\u51c6\u8bed\u6cd5\u3002\n\u6bd4\u5982\uff0c\u4e00\u4e2a\u7b80\u5355\u6570\u5b66\u8868\u8fbe\u5f0f\u8bed\u6cd5\u53ef\u80fd\u50cf\u4e0b\u9762\u8fd9\u6837\uff1a"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {},
      "outputs": [],
      "source": [
        "expr ::= expr + term\n    |   expr - term\n    |   term\n\nterm ::= term * factor\n    |   term / factor\n    |   factor\n\nfactor ::= ( expr )\n    |   NUM"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "\u6216\u8005\uff0c\u4ee5EBNF\u5f62\u5f0f\uff1a"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {},
      "outputs": [],
      "source": [
        "expr ::= term { (+|-) term }*\n\nterm ::= factor { (*|/) factor }*\n\nfactor ::= ( expr )\n    |   NUM"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "\u5728EBNF\u4e2d\uff0c\u88ab\u5305\u542b\u5728 {...}* \u4e2d\u7684\u89c4\u5219\u662f\u53ef\u9009\u7684\u3002*\u4ee3\u88680\u6b21\u6216\u591a\u6b21\u91cd\u590d(\u8ddf\u6b63\u5219\u8868\u8fbe\u5f0f\u4e2d\u610f\u4e49\u662f\u4e00\u6837\u7684)\u3002"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "\u73b0\u5728\uff0c\u5982\u679c\u4f60\u5bf9BNF\u7684\u5de5\u4f5c\u673a\u5236\u8fd8\u4e0d\u662f\u5f88\u660e\u767d\u7684\u8bdd\uff0c\u5c31\u628a\u5b83\u5f53\u505a\u662f\u4e00\u7ec4\u5de6\u53f3\u7b26\u53f7\u53ef\u76f8\u4e92\u66ff\u6362\u7684\u89c4\u5219\u3002\n\u4e00\u822c\u6765\u8bb2\uff0c\u89e3\u6790\u7684\u539f\u7406\u5c31\u662f\u4f60\u5229\u7528BNF\u5b8c\u6210\u591a\u4e2a\u66ff\u6362\u548c\u6269\u5c55\u4ee5\u5339\u914d\u8f93\u5165\u6587\u672c\u548c\u8bed\u6cd5\u89c4\u5219\u3002\n\u4e3a\u4e86\u6f14\u793a\uff0c\u5047\u8bbe\u4f60\u6b63\u5728\u89e3\u6790\u5f62\u5982 3 + 4 * 5 \u7684\u8868\u8fbe\u5f0f\u3002\n\u8fd9\u4e2a\u8868\u8fbe\u5f0f\u5148\u8981\u901a\u8fc7\u4f7f\u75282.18\u8282\u4e2d\u4ecb\u7ecd\u7684\u6280\u672f\u5206\u89e3\u4e3a\u4e00\u7ec4\u4ee4\u724c\u6d41\u3002\n\u7ed3\u679c\u53ef\u80fd\u662f\u50cf\u4e0b\u5217\u8fd9\u6837\u7684\u4ee4\u724c\u5e8f\u5217\uff1a"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {},
      "outputs": [],
      "source": [
        "NUM + NUM * NUM"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "\u5728\u6b64\u57fa\u7840\u4e0a\uff0c \u89e3\u6790\u52a8\u4f5c\u4f1a\u8bd5\u7740\u53bb\u901a\u8fc7\u66ff\u6362\u64cd\u4f5c\u5339\u914d\u8bed\u6cd5\u5230\u8f93\u5165\u4ee4\u724c\uff1a"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {},
      "outputs": [],
      "source": [
        "expr\nexpr ::= term { (+|-) term }*\nexpr ::= factor { (*|/) factor }* { (+|-) term }*\nexpr ::= NUM { (*|/) factor }* { (+|-) term }*\nexpr ::= NUM { (+|-) term }*\nexpr ::= NUM + term { (+|-) term }*\nexpr ::= NUM + factor { (*|/) factor }* { (+|-) term }*\nexpr ::= NUM + NUM { (*|/) factor}* { (+|-) term }*\nexpr ::= NUM + NUM * factor { (*|/) factor }* { (+|-) term }*\nexpr ::= NUM + NUM * NUM { (*|/) factor }* { (+|-) term }*\nexpr ::= NUM + NUM * NUM { (+|-) term }*\nexpr ::= NUM + NUM * NUM"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "\u4e0b\u9762\u6240\u6709\u7684\u89e3\u6790\u6b65\u9aa4\u53ef\u80fd\u9700\u8981\u82b1\u70b9\u65f6\u95f4\u5f04\u660e\u767d\uff0c\u4f46\u662f\u5b83\u4eec\u539f\u7406\u90fd\u662f\u67e5\u627e\u8f93\u5165\u5e76\u8bd5\u7740\u53bb\u5339\u914d\u8bed\u6cd5\u89c4\u5219\u3002\n\u7b2c\u4e00\u4e2a\u8f93\u5165\u4ee4\u724c\u662fNUM\uff0c\u56e0\u6b64\u66ff\u6362\u9996\u5148\u4f1a\u5339\u914d\u90a3\u4e2a\u90e8\u5206\u3002\n\u4e00\u65e6\u5339\u914d\u6210\u529f\uff0c\u5c31\u4f1a\u8fdb\u5165\u4e0b\u4e00\u4e2a\u4ee4\u724c+\uff0c\u4ee5\u6b64\u7c7b\u63a8\u3002\n\u5f53\u5df2\u7ecf\u786e\u5b9a\u4e0d\u80fd\u5339\u914d\u4e0b\u4e00\u4e2a\u4ee4\u724c\u7684\u65f6\u5019\uff0c\u53f3\u8fb9\u7684\u90e8\u5206(\u6bd4\u5982 { (*/) factor }* )\u5c31\u4f1a\u88ab\u6e05\u7406\u6389\u3002\n\u5728\u4e00\u4e2a\u6210\u529f\u7684\u89e3\u6790\u4e2d\uff0c\u6574\u4e2a\u53f3\u8fb9\u90e8\u5206\u4f1a\u5b8c\u5168\u5c55\u5f00\u6765\u5339\u914d\u8f93\u5165\u4ee4\u724c\u6d41\u3002"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "\u6709\u4e86\u524d\u9762\u7684\u77e5\u8bc6\u80cc\u666f\uff0c\u4e0b\u9762\u6211\u4eec\u4e3e\u4e00\u4e2a\u7b80\u5355\u793a\u4f8b\u6765\u5c55\u793a\u5982\u4f55\u6784\u5efa\u4e00\u4e2a\u9012\u5f52\u4e0b\u964d\u8868\u8fbe\u5f0f\u6c42\u503c\u7a0b\u5e8f\uff1a"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {},
      "outputs": [],
      "source": [
        "#!/usr/bin/env python\n# -*- encoding: utf-8 -*-\n\"\"\"\nTopic: \u4e0b\u964d\u89e3\u6790\u5668\nDesc :\n\"\"\"\nimport re\nimport collections\n\n# Token specification\nNUM = r'(?P<NUM>\\d+)'\nPLUS = r'(?P<PLUS>\\+)'\nMINUS = r'(?P<MINUS>-)'\nTIMES = r'(?P<TIMES>\\*)'\nDIVIDE = r'(?P<DIVIDE>/)'\nLPAREN = r'(?P<LPAREN>\\()'\nRPAREN = r'(?P<RPAREN>\\))'\nWS = r'(?P<WS>\\s+)'\n\nmaster_pat = re.compile('|'.join([NUM, PLUS, MINUS, TIMES,\n                                  DIVIDE, LPAREN, RPAREN, WS]))\n# Tokenizer\nToken = collections.namedtuple('Token', ['type', 'value'])\n\n\ndef generate_tokens(text):\n    scanner = master_pat.scanner(text)\n    for m in iter(scanner.match, None):\n        tok = Token(m.lastgroup, m.group())\n        if tok.type != 'WS':\n            yield tok\n\n\n# Parser\nclass ExpressionEvaluator:\n    '''\n    Implementation of a recursive descent parser. Each method\n    implements a single grammar rule. Use the ._accept() method\n    to test and accept the current lookahead token. Use the ._expect()\n    method to exactly match and discard the next token on on the input\n    (or raise a SyntaxError if it doesn't match).\n    '''\n\n    def parse(self, text):\n        self.tokens = generate_tokens(text)\n        self.tok = None  # Last symbol consumed\n        self.nexttok = None  # Next symbol tokenized\n        self._advance()  # Load first lookahead token\n        return self.expr()\n\n    def _advance(self):\n        'Advance one token ahead'\n        self.tok, self.nexttok = self.nexttok, next(self.tokens, None)\n\n    def _accept(self, toktype):\n        'Test and consume the next token if it matches toktype'\n        if self.nexttok and self.nexttok.type == toktype:\n            self._advance()\n            return True\n        else:\n            return False\n\n    def _expect(self, toktype):\n        'Consume next token if it matches toktype or raise SyntaxError'\n        if not self._accept(toktype):\n            raise SyntaxError('Expected ' + toktype)\n\n    # Grammar rules follow\n    def expr(self):\n        \"expression ::= term { ('+'|'-') term }*\"\n        exprval = self.term()\n        while self._accept('PLUS') or self._accept('MINUS'):\n            op = self.tok.type\n            right = self.term()\n            if op == 'PLUS':\n                exprval += right\n            elif op == 'MINUS':\n                exprval -= right\n        return exprval\n\n    def term(self):\n        \"term ::= factor { ('*'|'/') factor }*\"\n        termval = self.factor()\n        while self._accept('TIMES') or self._accept('DIVIDE'):\n            op = self.tok.type\n            right = self.factor()\n            if op == 'TIMES':\n                termval *= right\n            elif op == 'DIVIDE':\n                termval /= right\n        return termval\n\n    def factor(self):\n        \"factor ::= NUM | ( expr )\"\n        if self._accept('NUM'):\n            return int(self.tok.value)\n        elif self._accept('LPAREN'):\n            exprval = self.expr()\n            self._expect('RPAREN')\n            return exprval\n        else:\n            raise SyntaxError('Expected NUMBER or LPAREN')\n\n\ndef descent_parser():\n    e = ExpressionEvaluator()\n    print(e.parse('2'))\n    print(e.parse('2 + 3'))\n    print(e.parse('2 + 3 * 4'))\n    print(e.parse('2 + (3 + 4) * 5'))\n    # print(e.parse('2 + (3 + * 4)'))\n    # Traceback (most recent call last):\n    #    File \"<stdin>\", line 1, in <module>\n    #    File \"exprparse.py\", line 40, in parse\n    #    return self.expr()\n    #    File \"exprparse.py\", line 67, in expr\n    #    right = self.term()\n    #    File \"exprparse.py\", line 77, in term\n    #    termval = self.factor()\n    #    File \"exprparse.py\", line 93, in factor\n    #    exprval = self.expr()\n    #    File \"exprparse.py\", line 67, in expr\n    #    right = self.term()\n    #    File \"exprparse.py\", line 77, in term\n    #    termval = self.factor()\n    #    File \"exprparse.py\", line 97, in factor\n    #    raise SyntaxError(\"Expected NUMBER or LPAREN\")\n    #    SyntaxError: Expected NUMBER or LPAREN\n\n\nif __name__ == '__main__':\n    descent_parser()"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "### \u8ba8\u8bba\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "\u6587\u672c\u89e3\u6790\u662f\u4e00\u4e2a\u5f88\u5927\u7684\u4e3b\u9898\uff0c \u4e00\u822c\u4f1a\u5360\u7528\u5b66\u751f\u5b66\u4e60\u7f16\u8bd1\u8bfe\u7a0b\u65f6\u521a\u5f00\u59cb\u7684\u4e09\u5468\u65f6\u95f4\u3002\n\u5982\u679c\u4f60\u5728\u627e\u5bfb\u5173\u4e8e\u8bed\u6cd5\uff0c\u89e3\u6790\u7b97\u6cd5\u7b49\u76f8\u5173\u7684\u80cc\u666f\u77e5\u8bc6\u7684\u8bdd\uff0c\u4f60\u5e94\u8be5\u53bb\u770b\u4e00\u4e0b\u7f16\u8bd1\u5668\u4e66\u7c4d\u3002\n\u5f88\u663e\u7136\uff0c\u5173\u4e8e\u8fd9\u65b9\u9762\u7684\u5185\u5bb9\u592a\u591a\uff0c\u4e0d\u53ef\u80fd\u5728\u8fd9\u91cc\u5168\u90e8\u5c55\u5f00\u3002"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "\u5c3d\u7ba1\u5982\u6b64\uff0c\u7f16\u5199\u4e00\u4e2a\u9012\u5f52\u4e0b\u964d\u89e3\u6790\u5668\u7684\u6574\u4f53\u601d\u8def\u662f\u6bd4\u8f83\u7b80\u5355\u7684\u3002\n\u5f00\u59cb\u7684\u65f6\u5019\uff0c\u4f60\u5148\u83b7\u5f97\u6240\u6709\u7684\u8bed\u6cd5\u89c4\u5219\uff0c\u7136\u540e\u5c06\u5176\u8f6c\u6362\u4e3a\u4e00\u4e2a\u51fd\u6570\u6216\u8005\u65b9\u6cd5\u3002\n\u56e0\u6b64\u5982\u679c\u4f60\u7684\u8bed\u6cd5\u7c7b\u4f3c\u8fd9\u6837\uff1a"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {},
      "outputs": [],
      "source": [
        "expr ::= term { ('+'|'-') term }*\n\nterm ::= factor { ('*'|'/') factor }*\n\nfactor ::= '(' expr ')'\n    | NUM"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "\u4f60\u5e94\u8be5\u9996\u5148\u5c06\u5b83\u4eec\u8f6c\u6362\u6210\u4e00\u7ec4\u50cf\u4e0b\u9762\u8fd9\u6837\u7684\u65b9\u6cd5\uff1a"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {},
      "outputs": [],
      "source": [
        "class ExpressionEvaluator:\n    ...\n    def expr(self):\n    ...\n    def term(self):\n    ...\n    def factor(self):\n    ..."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "\u6bcf\u4e2a\u65b9\u6cd5\u8981\u5b8c\u6210\u7684\u4efb\u52a1\u5f88\u7b80\u5355 - \u5b83\u5fc5\u987b\u4ece\u5de6\u81f3\u53f3\u904d\u5386\u8bed\u6cd5\u89c4\u5219\u7684\u6bcf\u4e00\u90e8\u5206\uff0c\u5904\u7406\u6bcf\u4e2a\u4ee4\u724c\u3002\n\u4ece\u67d0\u79cd\u610f\u4e49\u4e0a\u8bb2\uff0c\u65b9\u6cd5\u7684\u76ee\u7684\u5c31\u662f\u8981\u4e48\u5904\u7406\u5b8c\u8bed\u6cd5\u89c4\u5219\uff0c\u8981\u4e48\u4ea7\u751f\u4e00\u4e2a\u8bed\u6cd5\u9519\u8bef\u3002\n\u4e3a\u4e86\u8fd9\u6837\u505a\uff0c\u9700\u91c7\u7528\u4e0b\u9762\u7684\u8fd9\u4e9b\u5b9e\u73b0\u65b9\u6cd5\uff1a"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "\u5c3d\u7ba1\u5411\u4f60\u6f14\u793a\u7684\u662f\u4e00\u4e2a\u7b80\u5355\u7684\u4f8b\u5b50\uff0c\u9012\u5f52\u4e0b\u964d\u89e3\u6790\u5668\u53ef\u4ee5\u7528\u6765\u5b9e\u73b0\u975e\u5e38\u590d\u6742\u7684\u89e3\u6790\u3002\n\u6bd4\u5982\uff0cPython\u8bed\u8a00\u672c\u8eab\u5c31\u662f\u901a\u8fc7\u4e00\u4e2a\u9012\u5f52\u4e0b\u964d\u89e3\u6790\u5668\u53bb\u89e3\u91ca\u7684\u3002\n\u5982\u679c\u4f60\u5bf9\u6b64\u611f\u5174\u8da3\uff0c\u4f60\u53ef\u4ee5\u901a\u8fc7\u67e5\u770bPython\u6e90\u7801\u6587\u4ef6Grammar/Grammar\u6765\u7814\u7a76\u4e0b\u5e95\u5c42\u8bed\u6cd5\u673a\u5236\u3002\n\u770b\u5b8c\u4f60\u4f1a\u53d1\u73b0\uff0c\u901a\u8fc7\u624b\u52a8\u65b9\u5f0f\u53bb\u5b9e\u73b0\u4e00\u4e2a\u89e3\u6790\u5668\u5176\u5b9e\u4f1a\u6709\u5f88\u591a\u7684\u5c40\u9650\u548c\u4e0d\u8db3\u4e4b\u5904\u3002"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "\u5176\u4e2d\u4e00\u4e2a\u5c40\u9650\u5c31\u662f\u5b83\u4eec\u4e0d\u80fd\u88ab\u7528\u4e8e\u5305\u542b\u4efb\u4f55\u5de6\u9012\u5f52\u7684\u8bed\u6cd5\u89c4\u5219\u4e2d\u3002\u6bd4\u5982\uff0c\u5047\u5982\u4f60\u9700\u8981\u7ffb\u8bd1\u4e0b\u9762\u8fd9\u6837\u4e00\u4e2a\u89c4\u5219\uff1a"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {},
      "outputs": [],
      "source": [
        "items ::= items ',' item\n    | item"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "\u4e3a\u4e86\u8fd9\u6837\u505a\uff0c\u4f60\u53ef\u80fd\u4f1a\u50cf\u4e0b\u9762\u8fd9\u6837\u4f7f\u7528 items() \u65b9\u6cd5\uff1a"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {},
      "outputs": [],
      "source": [
        "def items(self):\n    itemsval = self.items()\n    if itemsval and self._accept(','):\n        itemsval.append(self.item())\n    else:\n        itemsval = [ self.item() ]"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "\u552f\u4e00\u7684\u95ee\u9898\u662f\u8fd9\u4e2a\u65b9\u6cd5\u6839\u672c\u4e0d\u80fd\u5de5\u4f5c\uff0c\u4e8b\u5b9e\u4e0a\uff0c\u5b83\u4f1a\u4ea7\u751f\u4e00\u4e2a\u65e0\u9650\u9012\u5f52\u9519\u8bef\u3002"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "\u5173\u4e8e\u8bed\u6cd5\u89c4\u5219\u672c\u8eab\u4f60\u53ef\u80fd\u4e5f\u4f1a\u78b0\u5230\u4e00\u4e9b\u68d8\u624b\u7684\u95ee\u9898\u3002\n\u6bd4\u5982\uff0c\u4f60\u53ef\u80fd\u60f3\u77e5\u9053\u4e0b\u9762\u8fd9\u4e2a\u7b80\u5355\u627c\u8bed\u6cd5\u662f\u5426\u8868\u8ff0\u5f97\u5f53\uff1a"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {},
      "outputs": [],
      "source": [
        "expr ::= factor { ('+'|'-'|'*'|'/') factor }*\n\nfactor ::= '(' expression ')'\n    | NUM"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "\u8fd9\u4e2a\u8bed\u6cd5\u770b\u4e0a\u53bb\u6ca1\u5565\u95ee\u9898\uff0c\u4f46\u662f\u5b83\u5374\u4e0d\u80fd\u5bdf\u89c9\u5230\u6807\u51c6\u56db\u5219\u8fd0\u7b97\u4e2d\u7684\u8fd0\u7b97\u7b26\u4f18\u5148\u7ea7\u3002\n\u6bd4\u5982\uff0c\u8868\u8fbe\u5f0f \"3 + 4 * 5\" \u4f1a\u5f97\u523035\u800c\u4e0d\u662f\u671f\u671b\u768423.\n\u5206\u5f00\u4f7f\u7528\u201dexpr\u201d\u548c\u201dterm\u201d\u89c4\u5219\u53ef\u4ee5\u8ba9\u5b83\u6b63\u786e\u7684\u5de5\u4f5c\u3002"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "\u5bf9\u4e8e\u590d\u6742\u7684\u8bed\u6cd5\uff0c\u4f60\u6700\u597d\u662f\u9009\u62e9\u67d0\u4e2a\u89e3\u6790\u5de5\u5177\u6bd4\u5982PyParsing\u6216\u8005\u662fPLY\u3002\n\u4e0b\u9762\u662f\u4f7f\u7528PLY\u6765\u91cd\u5199\u8868\u8fbe\u5f0f\u6c42\u503c\u7a0b\u5e8f\u7684\u4ee3\u7801\uff1a"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {},
      "outputs": [],
      "source": [
        "from ply.lex import lex\nfrom ply.yacc import yacc\n\n# Token list\ntokens = [ 'NUM', 'PLUS', 'MINUS', 'TIMES', 'DIVIDE', 'LPAREN', 'RPAREN' ]\n# Ignored characters\nt_ignore = ' \\t\\n'\n# Token specifications (as regexs)\nt_PLUS = r'\\+'\nt_MINUS = r'-'\nt_TIMES = r'\\*'\nt_DIVIDE = r'/'\nt_LPAREN = r'\\('\nt_RPAREN = r'\\)'\n\n# Token processing functions\ndef t_NUM(t):\n    r'\\d+'\n    t.value = int(t.value)\n    return t\n\n# Error handler\ndef t_error(t):\n    print('Bad character: {!r}'.format(t.value[0]))\n    t.skip(1)\n\n# Build the lexer\nlexer = lex()\n\n# Grammar rules and handler functions\ndef p_expr(p):\n    '''\n    expr : expr PLUS term\n        | expr MINUS term\n    '''\n    if p[2] == '+':\n        p[0] = p[1] + p[3]\n    elif p[2] == '-':\n        p[0] = p[1] - p[3]\n\n\ndef p_expr_term(p):\n    '''\n    expr : term\n    '''\n    p[0] = p[1]\n\n\ndef p_term(p):\n    '''\n    term : term TIMES factor\n    | term DIVIDE factor\n    '''\n    if p[2] == '*':\n        p[0] = p[1] * p[3]\n    elif p[2] == '/':\n        p[0] = p[1] / p[3]\n\ndef p_term_factor(p):\n    '''\n    term : factor\n    '''\n    p[0] = p[1]\n\ndef p_factor(p):\n    '''\n    factor : NUM\n    '''\n    p[0] = p[1]\n\ndef p_factor_group(p):\n    '''\n    factor : LPAREN expr RPAREN\n    '''\n    p[0] = p[2]\n\ndef p_error(p):\n    print('Syntax error')\n\nparser = yacc()"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "\u8fd9\u4e2a\u7a0b\u5e8f\u4e2d\uff0c\u6240\u6709\u4ee3\u7801\u90fd\u4f4d\u4e8e\u4e00\u4e2a\u6bd4\u8f83\u9ad8\u7684\u5c42\u6b21\u3002\u4f60\u53ea\u9700\u8981\u4e3a\u4ee4\u724c\u5199\u6b63\u5219\u8868\u8fbe\u5f0f\u548c\u89c4\u5219\u5339\u914d\u65f6\u7684\u9ad8\u9636\u5904\u7406\u51fd\u6570\u5373\u53ef\u3002\n\u800c\u5b9e\u9645\u7684\u8fd0\u884c\u89e3\u6790\u5668\uff0c\u63a5\u53d7\u4ee4\u724c\u7b49\u7b49\u5e95\u5c42\u52a8\u4f5c\u5df2\u7ecf\u88ab\u5e93\u51fd\u6570\u5b9e\u73b0\u4e86\u3002"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "\u4e0b\u9762\u662f\u4e00\u4e2a\u600e\u6837\u4f7f\u7528\u5f97\u5230\u7684\u89e3\u6790\u5bf9\u8c61\u7684\u4f8b\u5b50\uff1a"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {},
      "outputs": [],
      "source": [
        "parser.parse('2')"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {},
      "outputs": [],
      "source": [
        "parser.parse('2+3')"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {},
      "outputs": [],
      "source": [
        "parser.parse('2+(3+4)*5')"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "\u5982\u679c\u4f60\u60f3\u5728\u4f60\u7684\u7f16\u7a0b\u8fc7\u7a0b\u4e2d\u6765\u70b9\u6311\u6218\u548c\u523a\u6fc0\uff0c\u7f16\u5199\u89e3\u6790\u5668\u548c\u7f16\u8bd1\u5668\u662f\u4e2a\u4e0d\u9519\u7684\u9009\u62e9\u3002\n\u518d\u6b21\uff0c\u4e00\u672c\u7f16\u8bd1\u5668\u7684\u4e66\u7c4d\u4f1a\u5305\u542b\u5f88\u591a\u5e95\u5c42\u7684\u7406\u8bba\u77e5\u8bc6\u3002\u4e0d\u8fc7\u5f88\u591a\u597d\u7684\u8d44\u6e90\u4e5f\u53ef\u4ee5\u5728\u7f51\u4e0a\u627e\u5230\u3002\nPython\u81ea\u5df1\u7684ast\u6a21\u5757\u4e5f\u503c\u5f97\u53bb\u770b\u4e00\u4e0b\u3002"
      ]
    }
  ],
  "metadata": {
    "kernelspec": {
      "display_name": "Python 3",
      "language": "python",
      "name": "python3"
    },
    "language_info": {
      "codemirror_mode": {
        "name": "ipython",
        "version": 3
      },
      "file_extension": ".py",
      "mimetype": "text/x-python",
      "name": "python",
      "nbconvert_exporter": "python",
      "pygments_lexer": "ipython3",
      "version": "3.7.1"
    },
    "toc": {
      "base_numbering": 1,
      "nav_menu": {},
      "number_sections": true,
      "sideBar": true,
      "skip_h1_title": true,
      "title_cell": "Table of Contents",
      "title_sidebar": "Contents",
      "toc_cell": false,
      "toc_position": {},
      "toc_section_display": true,
      "toc_window_display": true
    }
  },
  "nbformat": 4,
  "nbformat_minor": 2
}